package mht.leetCode.primary.array;

import java.util.HashSet;

/**
 * leetCode初级算法题目
 */

class Solution {

    /**
     * 【从排序数组中删除重复项】
     *
     * 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
     * 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
     *
     * 示例 1:
     * 给定数组 nums = [1,1,2],
     * 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
     * 你不需要考虑数组中超出新长度后面的元素。
     *
     * 实例 2：
     * 给定 nums = [0,0,1,1,1,2,2,3,3,4],
     * 函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
     * 你不需要考虑数组中超出新长度后面的元素。
     */
    public int removeDuplicates(int[] nums) {

        int res = 0;
        int l = nums.length;
        if (l == 0) {
            return 0;
        }

        if (l == 1) {
            return 1;
        }


        for (int i = 0; i < l; i++) {
            if (nums[i] != nums[res]) {
                res++;
                nums[res] = nums[i];
            }
        }

        res+=1;
        return res;
    }

    /**
     * 【买卖股票的最佳时机】
     *
     * 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
     * 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
     * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
     *
     * 示例如下：
     *
     * 输入: [7,1,5,3,6,4]
     * 输出: 7
     * 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     *      随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
     *
     * 输入: [1,2,3,4,5]
     * 输出: 4
     * 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     *      注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     *      因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
     *
     * 输入: [7,6,4,3,1]
     * 输出: 0
     * 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
     *
     */
    public int maxProfit(int[] prices) {

        // 思路：贪心算法，总是做出在当前看来是最好的选择，不从整体最优上加以考虑，也就是说，只关心当前最优解
        int maxPro = 0, tmp = 0;
        for (int i = 1; i < prices.length; ++i) {
            tmp = prices[i] - prices[i-1];
            if (tmp > 0)
                maxPro += tmp;
        }
        return maxPro;
    }

    /**
     * 买卖股票   只能交易一次
     */
    public int maxProfitOneTime(int[] prices) {

        // 暴力解法 O(n2)的时间复杂度
//        int res = 0;
//        for (int i = 0; i < prices.length; i++) {
//            for (int j = i; j < prices.length; j++) {
//                if (prices[j] - prices[i] > res) {
//                    res = prices[j] - prices[i];
//                }
//            }
//        }
//        return res;

        // O(n)时间复杂度
        if (prices == null || prices.length < 1) {
            return 0;
        }

        int max = 0;
        int min = prices[0];
        for (int price : prices) {
            if (price < min) {
                min = price;
            } else {
                if (max < price - min) {
                    max = price - min;
                }
            }
        }
        return max;
    }

    /**
     * 【旋转数组】
     *
     * 给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
     *
     * 示例 1:
     *
     * 输入: [1,2,3,4,5,6,7] 和 k = 3
     * 输出: [5,6,7,1,2,3,4]
     * 解释:
     * 向右旋转 1 步: [7,1,2,3,4,5,6]
     * 向右旋转 2 步: [6,7,1,2,3,4,5]
     * 向右旋转 3 步: [5,6,7,1,2,3,4]
     * 示例 2:
     *
     * 输入: [-1,-100,3,99] 和 k = 2
     * 输出: [3,99,-1,-100]
     * 解释:
     * 向右旋转 1 步: [99,-1,-100,3]
     * 向右旋转 2 步: [3,99,-1,-100]
     * 说明:
     *
     * 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
     * 要求使用空间复杂度为 O(1) 的 原地 算法。
     *
     */
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        int n;
        int temp1, temp2, index, count = 0;
        if (k >= len) {
            n = k % len;
        } else {
            n = k;
        }

        if (k == 0) {
            return;
        }

        for (int i = 0; i <= n; i++) {
            if(count >= len) {
                break;//对计数变量的控制，当所有位置全部移动完了就可以结束了
            }
            index = i;//每轮移动的初始下标
            temp1 = nums[i];
            while((index + k)%len != i) //一个while循环移动一次
            {
                temp2 = nums[(index + k)%len];
                nums[(index + k)%len] = temp1;
                index = (index + k)%len;
                temp1 = temp2;
                count++;
            }
            nums[i] = temp1;
            count++;
        }
    }

    /**
     * 【存在重复】
     *
     * 给定一个整数数组，判断是否存在重复元素。
     *
     * 如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。
     *
     * 示例 1:
     *
     * 输入: [1,2,3,1]
     * 输出: true
     * 示例 2:
     *
     * 输入: [1,2,3,4]
     * 输出: false
     * 示例 3:
     *
     * 输入: [1,1,1,3,3,4,3,2,4,2]
     * 输出: true
     *
     */
    public boolean containsDuplicate(int[] nums) {

        if (nums.length <= 1){
            return false;
        }

        HashSet set = new HashSet();


        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }

        if (set.size() == nums.length) {
            return false;
        } else
            return true;
    }

    /**
     * 【只出现一次的数字】
     *
     * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
     *
     * 说明：
     *
     * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
     *
     * 示例 1:
     *
     * 输入: [2,2,1]
     * 输出: 1
     * 示例 2:
     *
     * 输入: [4,1,2,1,2]
     * 输出: 4
     *
     */
    public int singleNumber(int[] nums) {
        //思路：根据异或运算的特点，相同的数字经过异或运算后结果为0，除单独出现一次的数字外，
        // 其他数字都是出现两次的，那么这些数字经过异或运算后结果一定是0。
        // 而任何数字与0进行异或运算都是该数字本身。
        // 所以对数组所有元素进行异或运算，运算结果就是题目的答案。
        int n = 0;
        for (int num : nums) {
            n = n ^ num;
        }
        return n;
    }

    /**
     * 【两个数组的交集】
     *
     * 给定两个数组，编写一个函数来计算它们的交集。
     *
     * 示例 1:
     *
     * 输入: nums1 = [1,2,2,1], nums2 = [2,2]
     * 输出: [2,2]
     * 示例 2:
     *
     * 输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
     * 输出: [4,9]
     *
     */
//    public int[] intersect(int[] nums1, int[] nums2) {
//
//    }

    /**
     * 【加一】
     *
     * 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
     *
     * 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
     *
     * 你可以假设除了整数 0 之外，这个整数不会以零开头。
     *
     * 示例 1:
     *
     * 输入: [1,2,3]
     * 输出: [1,2,4]
     * 解释: 输入数组表示数字 123。
     * 示例 2:
     *
     * 输入: [4,3,2,1]
     * 输出: [4,3,2,2]
     * 解释: 输入数组表示数字 4321。
     *
     */
    public int[] plusOne(int[] digits) {
        int carry = 1;

        for (int i = digits.length - 1; i >= 0; i--) {
            if (carry == 0) {
                return digits;
            }
            int tmp = digits[i] + carry;
            carry = tmp / 10;
            digits[i] = tmp % 10;
        }

        if (carry != 0) {
            int[] result = new int[digits.length + 1];
            result[0] = 1;
            return result;
        }

        return digits;
    }


    /**
     * 【移动零】
     *
     * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     *
     * 示例:
     *
     * 输入: [0,1,0,3,12]
     * 输出: [1,3,12,0,0]
     * 说明:
     *
     * 必须在原数组上操作，不能拷贝额外的数组。
     * 尽量减少操作次数。
     *
     */
    public void moveZeroes(int[] nums) {

        int count = 0;
        for (int i = 0; i < nums.length; i++) {

            if (nums[i] != 0) {
                nums[count] = nums[i];
                count++;
            }

        }
        for (int i = count; i < nums.length; i++) {
            nums[i] = 0;
        }

    }

    /**
     * 【两数之和】
     *
     * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
     *
     * 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
     *
     * 示例:
     *
     * 给定 nums = [2, 7, 11, 15], target = 9
     *
     * 因为 nums[0] + nums[1] = 2 + 7 = 9
     * 所以返回 [0, 1]
     */
    public int[] twoSum(int[] nums, int target) {


        int[] res = new int[2];

        for (int i = 0; i < nums.length; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    res[0] = i;
                    res[1] = j;
                }
            }
        }

        return res;
    }



    public static void main(String[] args) {
        int[] a = {0,1,0,3,12};
        Solution s = new Solution();
        s.moveZeroes(a);
    }
}
